package vip.zhenzicheng.algorithm.demo;

/**
 * 随机数题目
 *
 * @author zhenzicheng
 * @date: 2022-05-17 11:31
 */
public class RandToRand {
  public static void main(String[] args) {
    // 测试平方
    testPow2();

    // 则是黑盒
  }

  private static void testPow2() {
    int N = 10000;
    int count = 0;
    double x = 0.5;
    for (int i = 0; i < N; i++) {
      if (xToPower2() < x) {
        count++;
      }
    }
    System.out.println((double) count / N);
    System.out.println("x^2:" + Math.pow(x, 2));
  }

  /**
   * 将[0,1)的随机数概率变为x^2概率 相当于每一次在[0,1)的概率是x，两次都在就是x*x
   */
  public static double xToPower2() {
    return Math.max(Math.random(), Math.random());
  }


  private static class EqualProbability {
    /**
     * 该函数不能修改，固定返回[1-5]等概率的随机数
     */
    public static int f1() {
      return (int) (Math.random() * 5) + 1;
    }

    /**
     * 该函数不能修改，只能利用f1()，改造成等概率[0,1]
     */
    public static int f2() {
      int ans;
      do {
        ans = f1();
      } while (ans == 3);
      return ans < 3 ? 0 : 1;
    }

    /**
     * 通过改造f2()得到 000 ~ 111 二进制位等概率
     */
    public static int f3() {
      return (f2() << 2) + (f2() << 1) + (f2() << 0);
    }

    /**
     * 通过改造f3() 实现 [0,6]等概率返回
     */
    public static int f4() {
      int ans;
      do {
        ans = f3();
      } while (ans == 7);
      return ans;
    }

    /**
     * 出现[1-7]等概率返回
     */
    public static int g() {
      /*
       * 解法：1.将任意[a,b]上的黑盒函数改造成[0,1]上的等概率发生器，奇数左右各一半，中间值重做，偶数直接对半，再将[0,1]上等概率的发生器通过改造包装成指定[a,b]上等概率的函数
       * 2. 再通过左移运算，改造成二进制位上的等概率发生 比如 [0-39] 需要 2^x >= 39 此时x为需要的二进制位数
       */
      return f4() + 1;
    }
  }

  private static class UnequalProbability {

    /**
     * 以固定概率返回0和1，但是函数内容无法得知
     */
    public static int f() {
      return Math.random() < 0.84 ? 0 : 1;
    }

    /**
     * 现需要通过改造f()函数，使其能等概率返回 0 1
     */
    public static int g() {
      int ans;
      do {
        ans = f();
      } while (ans == f()); // 两次f()的结果如果相同重做，不同代表是 01 10，这两种情况是等概率的
      return ans;
    }

  }

}
